package org.example.myleet.rosalind.fib;

public class Solution {
    public long recurrence(int n, int k) {
        if (n <= 2) {
            return 1;
        }
        //第1会和，成熟：0，幼崽：1
        long i = 1, mate = 0, cub = 1, productiveMate;
        do {
            //增加1回合
            ++i;
            //可生产幼崽的成熟配对数量
            productiveMate = mate;
            //变成成熟配对的数量
            mate += cub;
            //生产出新的幼崽数
            cub = productiveMate * k;
        } while (i < n);
        //求总的配对数量
        return mate + cub;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
//        System.out.println(solution.recurrence(5, 3));
        System.out.println(solution.recurrence(29, 4));
    }
}
